package 每日一题;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/single-element-in-a-sorted-array/
 */
public class _540_有序数组中的单一元素 {
    /**
     * 两两相找  双指针
     * @param nums 目标数组
     * @return 查找的单一元素
     */
    public int singleNonDuplicate1(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        for (int i = 0; i < n - 1; i += 2) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums[n - 1];
    }

    /**
     * 二分法
     * 根据奇偶来判断方向，一般目标值的左边都是偶数，即 mid == mid + 1
     * 右边是奇数  mid == mid - 1
     * 因此通过奇偶就可以确定移动的方向
     * @param nums 目标数组
     * @return 查找的单一元素
     */
    public int singleNonDuplicate(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] == nums[mid ^ 1]) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return nums[l];
    }
}
